package solution;


import java.util.ArrayList;

/*
* 70 Array
*
* */
public class ClimbStairs {
    /*
    * 使用科学归纳法，动态规划证明
    * 使用数组对结果进行缓存
    * */
    public int solution1(int n){
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i < n + 1 ; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }


    /*
    * 推导出是斐波那契数列模型，直接使用通项公式
    *
    * */
    public int solution2(int n){
        double sqrt_5 = Math.sqrt(5);
        double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2, n + 1 );
        return (int)(fib_n / sqrt_5);
    }
}
